package com.zt.algorithm.sort;

public class InsertionSort {
    public static void main(String args[]){
        int a[] = new int[]{5,7,1,8,4};
        InsertionSort sort = new InsertionSort();
        sort.insertSort(a);
        for (int m:a) {
            System.out.print(m + ",");
        }

    }
    public void insertSort(int a[]){
        int i ,j;
        for(i=1;i<a.length;i++){
            if(a[i]<a[i-1]){//若a[i]大于等于有序区中所有的keys，则a[i]应在原有位置上
                int tem = a[i];
                j = i-1;
                do{ //从右向左在有序区a[1．．i-1]中查找a[i]的插入位置
                    a[j+1] = a[j];//将关键字大于a[i]的记录后移
                    j--;
                }while (j>=0 && tem < a[j] ) ;//当a[i]≥a[j].key时终止
                a[j+1] = tem; //a[i]插入到正确的位置上
            }
        }
    }
}
